#! /usr/bin/python3
# -*- coding: UTF-8 -*-
  
'''※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※
File Name: boolean_algebra.py
Author: GID5564
Description: 
Version: 1.0
Created Time: 08/12/24-14:14:09
※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※'''

def compare_string(string1, string2):
    """
    比较两个字符串，返回一个表示不同之处的字符串。如果不同之处超过一处，则返回-1。

    参数:
    string1 (str): 第一个字符串
    string2 (str): 第二个字符串

    返回值:
    str: 如果两个字符串只有一个字符不同，返回一个包含下划线的字符串，表示不同之处；
         如果有两个或更多字符不同，返回-1。

    示例:
    >>> compare_string('0010','0110')
    '0_10'

    >>> compare_string('0110','1101')
    -1
    """
    # 将字符串转换为列表以便修改
    l1 = list(string1)
    l2 = list(string2)
    count = 0  # 初始化计数器，用于记录不同字符的数量

    # 遍历字符串的每一个字符
    for i in range(len(l1)):
        if l1[i] != l2[i]:  # 如果对应位置的字符不同
            count += 1  # 计数器加一
            l1[i] = "_"  # 用下划线替换不同的字符

    # 如果不同字符数量大于1，返回-1
    if count > 1:
        return -1
    else:
        # 否则，将列表转换回字符串并返回
        return "".join(l1)
        
        
def check(binary):
    """
    检查并合并二进制字符串列表中的相似项。
    
    参数:
    binary (list of str): 包含二进制字符串的列表。
    
    返回:
    list of str: 合并后的二进制字符串列表。
    
    示例:
    >>> check(['0.00.01.5'])
    ['0.00.01.5']
    """
    pi = []  # 初始化结果列表
    while True:  # 无限循环，直到没有更多可合并的项
        check1 = ["$"] * len(binary)  # 初始化标记列表，用于记录哪些项已被处理
        temp = []  # 临时列表，用于存储合并后的新项
        for i in range(len(binary)):  # 遍历二进制字符串列表
            for j in range(i + 1, len(binary)):  # 从当前项的下一个开始比较
                k = compare_string(binary[i], binary[j])  # 比较两个二进制字符串
                if k != -1:  # 如果找到相似的项
                    check1[i] = "*"  # 标记该项已处理
                    check1[j] = "*"  # 标记该项已处理
                    temp.append(k)  # 将合并后的新项添加到临时列表中
        for i in range(len(binary)):  # 再次遍历二进制字符串列表
            if check1[i] == "$":  # 如果该项未被处理
                pi.append(binary[i])  # 将其添加到结果列表中
        if len(temp) == 0:  # 如果没有新的合并项
            return pi  # 返回最终的结果列表
        binary = list(set(temp))  # 更新二进制字符串列表为合并后的新项集合
       
def decimal_to_binary(no_of_variable, minterms):
    """
    将十进制数转换为二进制字符串表示。
    
    参数:
    no_of_variable (int): 变量的数量，即二进制字符串的长度。
    minterms (list of int): 需要转换的十进制数列表。
    
    返回:
    list of str: 每个十进制数对应的二进制字符串列表。
    
    示例:
    >>> decimal_to_binary(3, [1, 2, 3])
    ['001', '010', '011']
    """
    temp = []  # 用于存储转换后的二进制字符串
    s = ""     # 临时字符串，用于构建单个二进制字符串
    for m in minterms:  # 遍历每一个需要转换的十进制数
        for i in range(no_of_variable):  # 根据变量数量进行二进制转换
            s = str(m % 2) + s  # 取余数得到当前位的二进制值，并添加到字符串前面
            m //= 2  # 更新m为整除2后的值，准备计算下一位
        temp.append(s)  # 将构建好的二进制字符串添加到结果列表中
        s = ""  # 重置临时字符串，以便处理下一个十进制数
    return temp  # 返回所有转换后的二进制字符串列表
       
def is_for_table(string1, string2, count):
    """
    判断两个字符串在相同位置上有多少个字符不同，并检查这个数量是否等于给定的count值。

    参数:
    string1 (str): 第一个字符串。
    string2 (str): 第二个字符串。
    count (int): 期望的不同字符的数量。

    返回:
    bool: 如果不同字符的数量等于count，则返回True；否则返回False。

    示例:
    >>> is_for_table('__1','011',2)
    True

    >>> is_for_table('01_','001',1)
    False
    """
    # 将字符串转换为列表以便逐字符比较
    l1 = list(string1)
    l2 = list(string2)
    
    # 初始化计数器，用于记录不同字符的数量
    count_n = 0
    
    # 遍历字符串的每一个字符位置
    for i in range(len(l1)):
        # 如果对应位置的字符不同，则计数器加一
        if l1[i] != l2[i]:
            count_n += 1
    
    # 判断计数器的值是否等于给定的count值
    if count_n == count:
        return True
    else:
        return False
   
def selection(chart, prime_implicants):
    """
    根据给定的图表和质蕴涵项，选择并返回一个最小覆盖集。

    参数:
    chart (list of list of int): 二进制图表，表示每个质蕴涵项覆盖哪些最小项。
    prime_implicants (list of str): 质蕴涵项列表，与图表中的行对应。

    返回:
    list of str: 选择的质蕴涵项列表，构成最小覆盖集。

    示例:
    >>> selection([[1]], ['0.00.01.5'])
    ['0.00.01.5']

    >>> selection([[1]], ['0.00.01.5'])
    ['0.00.01.5']
    """
    temp = []  # 用于存储最终选择的质蕴涵项
    select = [0] * len(chart)  # 初始化选择标记数组，长度为图表的行数

    # 遍历图表的每一列
    for i in range(len(chart[0])):
        count = 0  # 计数器，记录当前列中值为1的元素个数
        rem = -1  # 记录最后一个值为1的元素所在的行索引
        for j in range(len(chart)):
            if chart[j][i] == 1:
                count += 1
                rem = j
        if count == 1:  # 如果当前列中只有一个值为1的元素
            select[rem] = 1  # 标记该元素对应的行为已选择

    # 根据标记数组更新图表，并添加相应的质蕴涵项到结果列表
    for i in range(len(select)):
        if select[i] == 1:
            for j in range(len(chart[0])):
                if chart[i][j] == 1:
                    for k in range(len(chart)):
                        chart[k][j] = 0  # 将该列的所有元素置为0
            temp.append(prime_implicants[i])  # 添加对应的质蕴涵项到结果列表

    # 循环处理剩余未覆盖的最小项
    while True:
        max_n = 0  # 记录当前最大覆盖数
        rem = -1  # 记录具有最大覆盖数的行索引
        count_n = 0  # 当前行的覆盖数
        for i in range(len(chart)):
            count_n = chart[i].count(1)  # 计算当前行的覆盖数
            if count_n > max_n:
                max_n = count_n
                rem = i

        if max_n == 0:  # 如果所有最小项都已覆盖
            return temp  # 返回结果列表

        temp.append(prime_implicants[rem])  # 添加具有最大覆盖数的质蕴涵项到结果列表

        # 更新图表，将该行覆盖的最小项置为0
        for i in range(len(chart[0])):
            if chart[rem][i] == 1:
                for j in range(len(chart)):
                    chart[j][i] = 0
   
def prime_implicant_chart(prime_implicants, binary):
    """
    生成素蕴涵项表。
    
    参数:
    prime_implicants (list of str): 素蕴涵项列表，每个元素是一个字符串表示的二进制数。
    binary (list of str): 二进制数列表，每个元素是一个字符串表示的二进制数。
    
    返回:
    list of list of int: 一个二维列表，表示素蕴涵项表。表中的元素为1或0，1表示该素蕴涵项覆盖对应的二进制数。
    
    示例:
    >>> prime_implicant_chart(['0.00.01.5'], ['0.00.01.5'])
    [[1]]
    """
    # 初始化素蕴涵项表，大小为 len(prime_implicants) x len(binary)，初始值为0
    chart = [[0 for x in range(len(binary))] for x in range(len(prime_implicants))]
    
    # 遍历每一个素蕴涵项
    for i in range(len(prime_implicants)):
        # 计算当前素蕴涵项中 '_' 的数量
        count = prime_implicants[i].count("_")
        
        # 遍历每一个二进制数
        for j in range(len(binary)):
            # 如果当前素蕴涵项可以覆盖当前的二进制数，则在表中标记为1
            if is_for_table(prime_implicants[i], binary[j], count):
                chart[i][j] = 1

    return chart

        
"""
#例:
def main():
    no_of_variable = int(input("Enter the no. of variables\n"))
    minterms = [
        int(x)
        for x in input(
            "Enter the decimal representation of Minterms 'Spaces Seprated'\n"
        ).split()
    ]
    binary = decimal_to_binary(no_of_variable, minterms)

    prime_implicants = check(binary)
    print("Prime Implicants are:")
    print(prime_implicants)
    chart = prime_implicant_chart(prime_implicants, binary)

    essential_prime_implicants = selection(chart, prime_implicants)
    print("Essential Prime Implicants are:")
    print(essential_prime_implicants)


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    main()

"""
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        